package previous.Test_0314;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //摆动序列
    public int wiggleMaxLength(int[] nums) {
        int n=nums.length;
        if(n==1) return 1;
        int[] f=new int[n];
        int[] g=new int[n];
        Arrays.fill(f,1);
        Arrays.fill(g,1);
        int ret=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]>nums[i]){
                    g[i]=Math.max(f[j]+1,g[i]);

                }
                if(nums[j]<nums[i]){
                    f[i]=Math.max(g[j]+1,f[i]);
                }
            }
            ret=Math.max(ret,Math.max(g[i],f[i]));
        }
        return ret;
    }
    //最长递增子序列个数
    public int findNumberOfLIS(int[] nums) {
           int n=nums.length;
           int[] f=new int[n];//长度
           int[] g=new int[n];//个数
           Arrays.fill(f,1);
           Arrays.fill(g,1);
           int length=1;
           int count=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]<nums[i]){
                    //奇数
                    if(f[j]+1==f[i]){
                       g[i]+=g[j];
                    }else if(f[j]+1>f[i])//重新计数
                    {
                        f[i]=f[j];
                        g[i]=g[j];
                    }
                }
            }
            if(length==f[i]){
               count+=g[i];
            } else if(length<f[i]){
               length= f[i];
               count= g[i];
            }
        }
        return count;
    }
    //迷宫中离路口最近的出路
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int nearestExit(char[][] maze, int[] entrance) {
        Queue<int[]> q=new LinkedList<>();
        int n=maze.length;
        int m=maze[0].length;
        q.add(new int[]{entrance[0],entrance[1]});
        boolean[][] vis=new boolean[n][m];
        vis[entrance[0]][entrance[1]]=true;
        int step=0;
        while(!q.isEmpty()){
            step++;
            int sz=q.size();
            for (int i = 0; i <sz ; i++) {
                int[] t=q.poll();
                int a=t[0];
                int b=t[1];
                for (int j = 0; j < 4; j++) {
                    int x=dx[j]+a;
                    int y=dy[j]+b;
                    if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && maze[x][y]=='.'){
                        //判断是否找到出口
                        if(x==0 || x==n-1 || y==0 || y==m-1) return step;
                        q.add(new int[]{x,y});
                        vis[x][y]=true;
                    }
                }
            }

        }
        return -1;
    }
    //最小基因变化
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> vis=new HashSet<>();
        Set<String> hash=new HashSet<>();
        char[] change={'A','C','T','G'};
        for(String x:bank){
            hash.add(x);
        }
        //首位相同，不变
        if(startGene.equals(endGene)) return 0;
        if(!hash.contains(endGene)) return -1;
        Queue<String> q=new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step=0;
        while(!q.isEmpty()){
            int sz=q.size();
            step++;
            for (int i = 0; i < sz; i++) {
                String t=q.poll();
                for (int j = 0; j < 8; j++) {
                    char[] tmp=t.toCharArray();
                    for (int k = 0; k < 4; k++) {
                        tmp[j]=change[k];
                        String next=new String(tmp);
                        if(hash.contains(next) && !vis.contains(next)){
                            if(next.equals(endGene)) return step;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }

        return -1;
    }
}
